package uestc.lj.midPromotion.compressedarray;

/**
 * 求数组的最大子数组和
 *
 * @Author:Crazlee
 * @Date:2021/12/3
 */
public class Code01_SubArrayMaxSum {
	public static int maxSum(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int maxValue = Integer.MIN_VALUE;
		int cur = 0;
		for (int array : arr) {
			cur += array;
			maxValue = Math.max(maxValue, cur);
			cur = Math.max(cur, 0);
		}
		return maxValue;
	}

	public static void main(String[] args) {
		int[] arr1 = { -2, -3, -5, 40, -10, -10, 100, 1 };
		System.out.println(maxSum(arr1));

		int[] arr2 = { -2, -3, -5, 0, 1, 2, -1 };
		System.out.println(maxSum(arr2));

		int[] arr3 = { -2, -3, -5, -1 };
		System.out.println(maxSum(arr3));

	}

}
